#ifndef SEARCH_HPP
#define SEARCH_HPP

#include "polygon.hpp"
#include "pattern.hpp"
#include <utility>
#include <vector>
#include <omp.h>
using namespace std;
#define block_size 40000
#define length_range 200000000
class Search{

    Pattern pattern;
    vector<Polygon> *polygons;
    // 分块大小
    // 按 polygon 的下边界 bottom 坐标分块，减少比对时间
//    vector<Polygon> polygons_split_by_y_bottom[length_range * 2 / block_size + 86];
//    vector<int> polygons_split_by_y_bottom_left_stack[length_range * 2 / block_size + 86];
//    vector<int> polygons_split_by_y_bottom_right_stack[length_range * 2 / block_size + 86];
    vector<MiniPolygon> mpolygons_split_by_y_bottom[length_range * 2 / block_size + 86];
    vector<Polygon*> polygons_split_by_y_bottom[length_range * 2 / block_size + 86];
    vector<int> mpolygons_split_by_y_bottom_left_stack[length_range * 2 / block_size + 86];
    vector<int> mpolygons_split_by_y_bottom_right_stack[length_range * 2 / block_size + 86];
    // 分块后剔除左右两侧空块
    int bottom_start, bottom_end;
    // 按 polygon 的上边界 top 坐标分块，减少比对时间
//    vector<Polygon> polygons_split_by_y_top[length_range * 2 / block_size + 86];
//    vector<int> polygons_split_by_y_top_left_stack[length_range * 2 / block_size + 86];
//    vector<int> polygons_split_by_y_top_right_stack[length_range * 2 / block_size + 86];
    vector<MiniPolygon> mpolygons_split_by_y_top[length_range * 2 / block_size + 86];
    vector<Polygon*> polygons_split_by_y_top[length_range * 2 / block_size + 86];
    vector<int> mpolygons_split_by_y_top_left_stack[length_range * 2 / block_size + 86];
    vector<int> mpolygons_split_by_y_top_right_stack[length_range * 2 / block_size + 86];
    // 分块后剔除左右两侧空块
    int top_start, top_end;


    int thread_cnt;


    vector<Pattern> ans;
    bool rotate_flag;
public:
    //构造
    Search(Pattern pat, vector<Polygon> *ps, bool rot = false, int thread_cnt = 1) {
        this->thread_cnt = thread_cnt;

        pattern = std::move(pat);
        polygons = ps;
        rotate_flag = rot;
        auto get_id = [&](int x){
            return (x + length_range) / block_size + 1;
        };

        if (thread_cnt <= 1) {
            for(auto &polygon: *polygons){
                int id = get_id(polygon.get_bottom());
                if (mpolygons_split_by_y_bottom[id].empty()) {
                    mpolygons_split_by_y_bottom[id].reserve(128);
                    polygons_split_by_y_bottom[id].reserve(128);
                }
                mpolygons_split_by_y_bottom[id].emplace_back(polygon.left, polygon.right, polygon.top, polygon.bottom);
                polygons_split_by_y_bottom[id].push_back(&polygon);

                id = get_id(polygon.get_top());
                if (mpolygons_split_by_y_top[id].empty()) {
                    mpolygons_split_by_y_top[id].reserve(128);
                    polygons_split_by_y_top[id].reserve(128);
                }
                mpolygons_split_by_y_top[id].emplace_back(polygon.left, polygon.right, polygon.top, polygon.bottom);
                polygons_split_by_y_top[id].push_back(&polygon);
            }
        } else {
            if (thread_cnt >= 4) { // NOLINT(bugprone-branch-clone)
#pragma omp parallel for num_threads(4)
                for (int i = 0; i < 4; i++) {
                    if (i == 0) {
                        for(auto const &polygon: *polygons){
                            int id = get_id(polygon.get_bottom());
                            if (mpolygons_split_by_y_bottom[id].empty()) {
                                mpolygons_split_by_y_bottom[id].reserve(128);
                            }
                            mpolygons_split_by_y_bottom[id].emplace_back(polygon.left, polygon.right, polygon.top, polygon.bottom);
                        }
                    }
                    if (i == 1) {
                        for(auto &polygon: *polygons){
                            int id = get_id(polygon.get_bottom());
                            if (polygons_split_by_y_bottom[id].empty()) {
                                polygons_split_by_y_bottom[id].reserve(128);
                            }
                            polygons_split_by_y_bottom[id].push_back(&polygon);
                        }
                    }
                    if (i == 2) {
                        for(auto const &polygon: *polygons){
                            int id = get_id(polygon.get_top());
                            if (mpolygons_split_by_y_top[id].empty()) {
                                mpolygons_split_by_y_top[id].reserve(128);
                            }
                            mpolygons_split_by_y_top[id].emplace_back(polygon.left, polygon.right, polygon.top, polygon.bottom);
                        }
                    }
                    if (i == 3) {
                        for(auto &polygon: *polygons){
                            int id = get_id(polygon.get_top());
                            if (polygons_split_by_y_top[id].empty()) {
                                polygons_split_by_y_top[id].reserve(128);
                            }
                            polygons_split_by_y_top[id].push_back(&polygon);
                        }
                    }
                }
            } else {
#pragma omp parallel for num_threads(2)
                for (int i = 0; i < 2; i++) {
                    if (i == 0) {
                        for(auto &polygon: *polygons){
                            int id = get_id(polygon.get_bottom());
                            if (mpolygons_split_by_y_bottom[id].empty()) {
                                mpolygons_split_by_y_bottom[id].reserve(128);
                                polygons_split_by_y_bottom[id].reserve(128);
                            }
                            mpolygons_split_by_y_bottom[id].emplace_back(polygon.left, polygon.right, polygon.top, polygon.bottom);
                            polygons_split_by_y_bottom[id].push_back(&polygon);
                        }
                    } else {
                        for(auto &polygon: *polygons){
                            int id = get_id(polygon.get_top());
                            if (mpolygons_split_by_y_top[id].empty()) {
                                mpolygons_split_by_y_top[id].reserve(128);
                                polygons_split_by_y_top[id].reserve(128);
                            }
                            mpolygons_split_by_y_top[id].emplace_back(polygon.left, polygon.right, polygon.top, polygon.bottom);
                            polygons_split_by_y_top[id].push_back(&polygon);
                        }
                    }
                }
            }
        }


        bottom_start = 0, bottom_end = length_range * 2 / block_size + 1;
        while(mpolygons_split_by_y_bottom[bottom_start].empty()) bottom_start++;
        while(mpolygons_split_by_y_bottom[bottom_end].empty()) bottom_end--;

        for(int i = bottom_start; i <= bottom_end; i++){
            int len = mpolygons_split_by_y_bottom[i].size();
            mpolygons_split_by_y_bottom_left_stack[i].reserve(len);
            mpolygons_split_by_y_bottom_right_stack[i].reserve(len);
            for(int j = 0; j < len; j++){
                mpolygons_split_by_y_bottom_left_stack[i].emplace_back(max(
                    mpolygons_split_by_y_bottom[i][j].right, j == 0 ? -length_range : mpolygons_split_by_y_bottom_left_stack[i][j - 1]));
            }
            for(int j = 0; j < len; j++){
                mpolygons_split_by_y_bottom_right_stack[i].emplace_back(min(
                    mpolygons_split_by_y_bottom[i][len - j - 1].left, j == len - 1 ? length_range : mpolygons_split_by_y_bottom_right_stack[i][j - 1]));
            }
            reverse(mpolygons_split_by_y_bottom_right_stack[i].begin(), mpolygons_split_by_y_bottom_right_stack[i].end());
        }

        top_start = 0, top_end = length_range * 2 / block_size + 1;
        while(mpolygons_split_by_y_top[top_start].empty()) top_start++;
        while(mpolygons_split_by_y_top[top_end].empty()) top_end--;

        for(int i = top_start; i <= top_end; i++){
            int len = mpolygons_split_by_y_top[i].size();
            mpolygons_split_by_y_top_left_stack[i].reserve(len);
            mpolygons_split_by_y_top_right_stack[i].reserve(len);
            for(int j = 0; j < len; j++){
                mpolygons_split_by_y_top_left_stack[i].emplace_back(max(
                    mpolygons_split_by_y_top[i][j].right, j == 0 ? -length_range : mpolygons_split_by_y_top_left_stack[i][j - 1]));
            }
            for(int j = 0; j < len; j++){
                mpolygons_split_by_y_top_right_stack[i].emplace_back(min(
                    mpolygons_split_by_y_top[i][len - j - 1].left, j == len - 1 ? length_range : mpolygons_split_by_y_top_right_stack[i][j - 1]));
            }
            reverse(mpolygons_split_by_y_top_right_stack[i].begin(), mpolygons_split_by_y_top_right_stack[i].end());
        }
    }


    Pattern create_pattern(Point left_node, int width, int height) {
        vector<Polygon> ps;
        int l = left_node.get_x();
        int r = l + width;
        int b = left_node.get_y();
        int t = b + height;

        auto get_id = [&](int x){
            return (int)((x + length_range) / block_size + 1);
        };

        int bottom_len = min(bottom_end, get_id(t)) - bottom_start;
        int top_len = top_end - max(top_start, get_id(b));

        if(bottom_len < top_len)
            for (int id = bottom_start; id <= min(bottom_end, get_id(t)); id++){

                int start_id = lower_bound(
                    mpolygons_split_by_y_bottom_left_stack[id].begin(), mpolygons_split_by_y_bottom_left_stack[id].end(), l) -
                    mpolygons_split_by_y_bottom_left_stack[id].begin();
                int end_id = lower_bound(
                    mpolygons_split_by_y_bottom_right_stack[id].begin(), mpolygons_split_by_y_bottom_right_stack[id].end(), r + 1) -
                    mpolygons_split_by_y_bottom_right_stack[id].begin();

                auto data = mpolygons_split_by_y_bottom[id].data();
                for (int i = start_id; i < end_id; i++) {
                    if ((data + i)->judge_conflict_square(l, r, b, t)) {
                        vector<Polygon> sub_ps = polygons_split_by_y_bottom[id][i]->get_conflict_polygons(l, r, b, t);
                        //获得相交的矩形，并压入ps内
                        if (!sub_ps.empty())
                            ps.insert(ps.end(), sub_ps.begin(), sub_ps.end());
                    }
                    if (i % 4 == 0 && i + 4 < end_id) {
                        __builtin_prefetch(data + i + 4, 0, 2);
                    }
                }
            }

        else{
            for (int id = max(top_start, get_id(b)); id <= top_end; id++){

                int start_id = lower_bound(
                    mpolygons_split_by_y_top_left_stack[id].begin(), mpolygons_split_by_y_top_left_stack[id].end(), l) -
                    mpolygons_split_by_y_top_left_stack[id].begin();
                int end_id = lower_bound(
                    mpolygons_split_by_y_top_right_stack[id].begin(), mpolygons_split_by_y_top_right_stack[id].end(), r + 1) -
                    mpolygons_split_by_y_top_right_stack[id].begin();

                auto data = mpolygons_split_by_y_top[id].data();
                for (int i = start_id; i < end_id; i++) {
                    if (__builtin_expect((data + i)->judge_conflict_square(l, r, b, t), 0)) {
                        vector<Polygon> sub_ps = polygons_split_by_y_top[id][i]->get_conflict_polygons(l, r, b, t);
                        //获得相交的矩形，并压入ps内
                        if (!sub_ps.empty())
                            ps.insert(ps.end(), sub_ps.begin(), sub_ps.end());
                    }
                    if (i % 4 == 0 && i + 4 < end_id) {
                        __builtin_prefetch(data + i + 4, 0, 2);
                    }
                }
            }
        }
        Pattern p = Pattern(ps, width, height);
        return p;
    }

    //search_first 利用pat里面最复杂的多边形进行匹配，返回所有画出来的pattern的左下角位置和镜像方位（注意patten框横过来）
    void search_first(Pattern rot_pattern) {
        Polygon nb_polygon = rot_pattern.get_nb_polygon();
        int static_id = nb_polygon.get_static_node_id();
        if (thread_cnt <= 1) {
            for (auto &i: *polygons){
                int match_id;
                if (~(match_id = nb_polygon.move_equal(i))) {
                    //得到边框左下角位置
                    Point p = i.get_node(match_id) + i.get_left_node() - nb_polygon.get_node(static_id) - nb_polygon.get_left_node();
                    Pattern candidate = create_pattern(p, rot_pattern.get_width(), rot_pattern.get_height());
                    candidate.set_left_node(p);
                    candidate.normalization();
                    //if(i % 100 == 0)
                    //    printf("%d ", i);
                    if (candidate == rot_pattern)
                        ans.push_back(candidate);
                }
            }
        } 
        else{
            const int bf_sz = 16;
            vector<vector<Pattern>*> candidates;
            for (int i = 0; i < thread_cnt; i++) {
                candidates.push_back(new vector<Pattern>());
                candidates[i]->reserve(bf_sz);
            }
            ans.reserve(100000);
#pragma omp parallel for num_threads(thread_cnt) schedule(static)
            for (auto &i: *polygons){
                int match_id;
                if (~(match_id = nb_polygon.move_equal(i))) {
                    //得到边框左下角位置
                    Point p = i.get_node(match_id) + i.get_left_node() - nb_polygon.get_node(static_id) - nb_polygon.get_left_node();
                    Pattern candidate = create_pattern(p, rot_pattern.get_width(), rot_pattern.get_height());
                    candidate.set_left_node(p);
                    candidate.normalization();
                    if (candidate == rot_pattern){
                        int id = omp_get_thread_num();
                        candidates[id]->push_back(candidate);
                        if (id > 0 && candidates[id]->size() == bf_sz) {
#pragma omp critical
                            ans.insert(ans.end(), make_move_iterator(candidates[id]->begin()), make_move_iterator(candidates[id]->end()));
                            candidates[id]->clear();
                            candidates[id]->reserve(bf_sz);
                        }
                    }
                }
            }
            for (int i = 0; i < thread_cnt; i++) {
                ans.insert(ans.end(), make_move_iterator(candidates[i]->begin()), make_move_iterator(candidates[i]->end()));
            }
        }
        //cout << "candidates:" << endl;

        //cout << endl;
    }

    //搜索入口，先search_first，然后判断每一个是否合法，返回ans
    void solve() {
        //pattern.printf();
        int max_k = 1;
        if (rotate_flag)
            max_k = 8;
        search_first(pattern);
        for (int i = 1; i < max_k; i++) {
            //cout << "rot_type = " << i << endl;
            Pattern rot_pattern = pattern.get_rotate(i);
            //rot_pattern.printf();
            //cout << "nb_polygon:" << endl;
            //rot_pattern.get_nb_polygon().printf();
            //cout << endl;
            search_first(rot_pattern);
        }

    }
    void print_ans(FILE *f) {
        for (auto & an : ans) {
            an.print_bound(f);
        }
    }
};

#endif